package com.neteasy.interview;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * @author ZhangyiA
 * @describe: 二分图最小顶点覆盖
 * https://www.cnblogs.com/jianglangcaijin/p/6035945.html
 * 最小顶点覆盖等于二分图最大匹配边 , 左边标记的点全都为匹配边的顶点 , 因为我们构造路径的时候左边的点向右找的边是最大匹配的边;
 * 右边未标记的点也为二分图最大匹配边的顶点 ，即左边标记的点加上右边未标记的点正好是最大匹配数目 。
 * @date 2021/07/07
 */

public class Three_ProjectManager {

    private Map<Integer , ArrayList<Integer>> graph ;
    private  boolean[] vis;
    private int[] match;

    public Three_ProjectManager(){}

    public void init(Map<Integer , ArrayList<Integer>> graph , boolean[] vis , int[] match){
        this.graph = graph;
        this.vis = vis;
        this.match = match;
    }

    public int[] read(Scanner input){
        String str = input.nextLine();
        String[] buff = str.split(" ");
        int[] num = new int[buff.length];
        for(int i = 0 ; i < buff.length ; i ++){
            num[i] = Integer.parseInt(buff[i]);
        }
        return num;
    }

    public int getMinimumVertexCover(int[] A){
        int ans = 0;
        Arrays.fill(match , -1);
        for(int i = 0 ; i < A.length ; i++){
            if(match[A[i]] == -1){
                Arrays.fill(vis , false);
                if(dfs(A[i])) ans ++;
            }
        }
        return ans;
    }

    public boolean dfs(int u){
        for(int v : graph.get(u)){
            if(!vis[v]){
                vis[v] = true;
                if(match[v] == -1 || dfs(match[v])){
                    match[u] = v;
                    match[v] = u;
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        Three_ProjectManager manager = new Three_ProjectManager();
        int[] A = manager.read(input);
        int[] B = manager.read(input);
        int n = input.nextInt();
        Map<Integer , ArrayList<Integer>> graph = new HashMap<>();
        int max_value = -1;
        for(int i = 1 ; i <= n ; i ++){
            int u = input.nextInt();
            int v = input.nextInt();
            int m = u > v ? u : v;
            max_value = Math.max(max_value , m);
            ArrayList<Integer> temp =  graph.containsKey(u) ? graph.get(u) : new ArrayList<>();
            temp.add(v);
            graph.put(u , temp);
            ArrayList<Integer> temp2 = graph.containsKey(v) ? graph.get(v) : new ArrayList<>();
            temp2.add(u);
            graph.put(v , temp2);
        }
        boolean[] vis = new boolean[max_value + 1];
        int[] match = new int[max_value + 1];
        manager.init(graph , vis , match);
        System.out.println(manager.getMinimumVertexCover(A));
    }
}

/*
1 2 3 4
5 6 7 8 9
8
1 7
2 5
2 6
2 8
3 7
4 7
4 8
4 9
* */